//
//  126_斐波那契数.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/3.
//

import UIKit

class FeiboNaQie: NSObject {
    
    /// 递归实现（空间复杂度2的n次方，空间复杂度O（n））
    /// - Parameter n: 第几个数
    /// - Returns: 结果
    func fib1(_ n: Int) -> Int {
        if n <= 2 {
            return 1
        }
        return fib1(n-1) + fib1(n - 2)
    }
//    迭代实现
    func fib(_ n: Int) -> Int {
        if n == 0 {
            return 0
        }
        var first = 0
        var second = 1
        var index = 2
        while index <= n {
            let temp = second
            second = (first + second) % 1000000007
            first = temp
            index += 1
        }
        return second
    }
}
